package leetcode.editor.cn;

//给你两个 非空 的链表，表示两个非负的整数。它们每位数字都是按照 逆序 的方式存储的，并且每个节点只能存储 一位 数字。 
//
// 请你将两个数相加，并以相同形式返回一个表示和的链表。 
//
// 你可以假设除了数字 0 之外，这两个数都不会以 0 开头。 
//
// 
//
// 示例 1： 
//
//
//输入：l1 = [2,4,3], l2 = [5,6,4]
//输出：[7,0,8]
//解释：342 + 465 = 807.
//
//
// 示例 2：
//
//
//输入：l1 = [0], l2 = [0]
//输出：[0]
//
//
// 示例 3：
//
//
//输入：l1 = [9,9,9,9,9,9,9], l2 = [9,9,9,9]
//输出：[8,9,9,9,0,0,0,1]
//
//
//
//
// 提示：
//
//
// 每个链表中的节点数在范围 [1, 100] 内
// 0 <= Node.val <= 9
// 题目数据保证列表表示的数字不含前导零
//
// Related Topics 递归 链表 数学 👍 7932 👎 0

public class 两数相加2 {
    public static void main(String[] args) {
        Solution solution = new 两数相加2().new Solution();
        两数相加2 两数相加2 = new 两数相加2();

        ListNode l1 = 两数相加2.new ListNode(9);
        ListNode l2 = 两数相加2.new ListNode(1,两数相加2.new ListNode(9,两数相加2.new ListNode(9,两数相加2.new ListNode(9,两数相加2.new ListNode(9,两数相加2.new ListNode(9,两数相加2.new ListNode(9,两数相加2.new ListNode(9,两数相加2.new ListNode(9,两数相加2.new ListNode(9))))))))));
        ListNode listNode = solution.addTwoNumbers(l1, l2);
        while (listNode != null) {
            System.out.print(listNode.val);
            listNode = listNode.next;
        }
        System.out.println();
    }

//leetcode submit region begin(Prohibit modification and deletion)


    class Solution {
        public ListNode addTwoNumbers(ListNode l1, ListNode l2) {
            ListNode prev = new ListNode(0);
            ListNode curr = prev;
            int carry = 0;
            while (l1 != null || l2 != null){
                int x = l1 != null ? l1.val : 0;
                int y = l2 != null ? l2.val : 0;
                int sum  = x + y + carry;
                carry = sum / 10 ;
                sum = sum % 10;
                curr.next = new ListNode(sum);

                curr = curr.next;
                if (l1 != null){
                    l1 = l1.next;
                }
                if (l2 != null){
                    l2 = l2.next;
                }
            }
            if (carry == 1){
                curr.next = new ListNode(carry);
            }
            return prev.next;

        }

        public ListNode addTwoNumbers1(ListNode l1, ListNode l2) {
            ListNode listNode = null;
            long nodeL1 = nodeToNum(0, l1,1);
            long nodeL2 = nodeToNum(0, l2,1);
            long sum = (long) (nodeL1 + nodeL2);
            char[] chars = String.valueOf(sum).toCharArray();
            ListNode upNode = null;
            for (int i = 1; i <= chars.length; i++) {
                ListNode currentNode = new ListNode(Integer.parseInt(String.valueOf(chars[chars.length - i])));
                // 设置头元素
                if (upNode == null) {
                    listNode = currentNode;
                    upNode = currentNode;
                    continue;
                }
                upNode.next = currentNode;
                upNode = currentNode;
            }
            return listNode;
        }

        /**
         * 链表转换成 int 数值
         *
         * @param tNum  头元素
         * @param node  当天节点
         * @return
         */
        long nodeToNum(long tNum, ListNode node,int index) {
            if (node == null) {
                return 0;
            }
            long power = power(index);
            long num = node.val * power;
            tNum = tNum + num;
            if (node.next != null) {
                index++;
                return nodeToNum(tNum, node.next,index);
            }
            return tNum;
        }

        long power(int index) {
            int powerNum = 1;
            while (index > 1) {
                powerNum = powerNum * 10;
                index--;
            }
            return powerNum;
        }

    }
//leetcode submit region end(Prohibit modification and deletion)

    /**
     * Definition for singly-linked list.
     */
    class ListNode {
        int val;
        ListNode next;

        ListNode() {
        }

        ListNode(int val) {
            this.val = val;
        }

        ListNode(int val, ListNode next) {
            this.val = val;
            this.next = next;
        }
    }

}
